﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/
/*
题目描述：
已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，
使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。
如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
你必须尽可能减少整个操作步骤。

示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
 
提示：
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104
 
进阶：
这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
*/

// 方法——二分搜索
/*
思路：
对于数组中有重复元素的情况，二分查找时，可能会出现nums[left] == nums[mid] && nums[mid[ == nums[right]
这时候就没法判断[left, mid]和[mid + 1, right]哪个区间是有序的了。
对于这种情况我们其实只需要继续在[left + 1, right - 1]继续二分即可。因为如果nums[left] == nums[right] == nums[mid]，那么
[left, right] 和[left + 1, right - 1]这两个区间就是等价的。
*/


// 有了以上思路，那我们写起代码来也就水到渠成了
// 先写一个递归版本的二分查找
bool binary_search(int* nums, int left, int right, int target) {
    assert(nums);
    if (left > right) {
        return false;
    }
    int mid = left + (right - left) / 2;
    if (nums[left] == target) {
        return true;
    }
    else if (nums[mid] == target) {
        return true;
    }
    else if (nums[right] == target) {
        return true;
    }
    else if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
        return binary_search(nums, left + 1, right - 1, target);
    }
    else if (nums[left] < nums[mid]) {
        if (target > nums[left] && target < nums[mid]) {
            return binary_search(nums, left + 1, mid - 1, target);
        }
        else {
            return binary_search(nums, mid + 1, right - 1, target);
        }
    }
    else if (nums[mid + 1] <= nums[right]) {
        if (target >= nums[mid + 1] && target <= nums[right]) {
            return binary_search(nums, mid + 1, right - 1, target);
        }
        else {
            return binary_search(nums, left + 1, mid - 1, target);
        }
    }
    return false;
}
bool search1(int* nums, int numsSize, int target) {
    assert(nums);
    return binary_search(nums, 0, numsSize - 1, target);
}

// 迭代版
bool search2(int* nums, int numsSize, int target) {
    assert(nums);
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return true;
        }
        if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
            left++;
            right--;
        }
        else if (nums[left] <= nums[mid]) {
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        else {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
    }
    return false;
}

int main() {
    int nums[] = { 4, 5, 6, 7, 8, 0, 0, 1, 1, 2, 3, 3, 4, 4 };
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int target = 8;
    int result = 0;
    result = search2(nums, numsSize, target);
    printf("%d\n", result);
    return 0;
}